package com.company;

/**
 * @author zhf
 * @date 2021/10/29
 */

import java.util.Arrays;

/**
 *
 *接雨水
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 * 使用双指针
 *
 */
public class Rain {
    public static void main(String[] args) {
        Rain rain = new Rain();
        int[] height = new int[]{4,2,0,3,2,5};
        int ans = rain.trap(height);
        System.out.println(ans);

    }
    public int trap(int[] height) {
        int sum = 0;
        int leftMax = 0, rightMax = 0;
        int left = 0, right = height.length-1;
        /**
         * 双指针
         * 如果左边的height值比右边的小，当前能储水量为leftMax = leftMax - height【left】，同时左指针右移；
         * 右边的同理；
         */
        while (left < right){
            leftMax = Math.max(leftMax,height[left]);
            rightMax = Math.max(rightMax,height[right]);
            if (height[left] < height[right]){
                sum = sum + (leftMax - height[left]);
                left++;
            }else {
                sum = sum + (rightMax - height[right]);
                right--;
            }
        }
        return sum;
    }
}
